package array;

import java.util.Random;

public class KSelect {
	
	//nlogk
	public static int select(int[] array, int i, int start, int end)
			throws Exception {
		if (array == null)
			throw new Exception();
		if (start == end)
			return array[start];

		int pIndex = random_partition(array, start, end);
		int k = pIndex - start + 1;
		if (i == k)
			return array[pIndex];
		else if (i < k)
			return select(array, i, start, pIndex - 1);
		else
			return select(array, i - k, pIndex + 1, end);
	}

	//like the quick sort
	public static int random_partition(int[] array, int start, int end) {
		Random r = new Random();
		int pIndex = start + r.nextInt(end - start);
		int temp = array[end];
		array[end] = array[pIndex];
		array[pIndex] = temp;

		return partition(array, start, end);

	}

	public static int partition(int[] array, int start, int end) {
		int pivot = array[end];
		int i = start - 1;
		for (int j = start; j < end - 1; j++) {
			if (array[j] <= pivot) {
				i++;
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[i + 1];
		array[i + 1] = array[end];
		array[end] = temp;

		return i + 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = new int[]{10,1,2,6,4,5,3, 18};
		try {
			System.out.println(select(array, 3, 0, 6));
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}
